#pragma once

#ifndef __CANVAS_COLLECTION_LIST_H
#define __CANVAS_COLLECTION_LIST_H

#include "..\Objects.h"
#include "Interface.h"
#include <string.h>
namespace Canvas
{
	namespace Collection
	{
		template<class T, bool PodType>
		class ListStore abstract : public Object {};

		template<class T>
		class ListStore<T, false>
		{
		protected:
			static void CopyObjects(T* dest, const T* source, int count)
			{
				if (dest < source)
				{
					for (int i = 0; i < count; i++)
					{
						dest[i] = MoveValue(source[i]);
					}
				}
				else if(dest > source)
				{
					for (int i = count - 1; i >= 0; i--)
					{
						dest[i] = MoveValue(source[i]);
					}
				}
			}

			static void ClearObjects(T* dest, int count)
			{
				for (int i = 0; i < count; i++)
				{
					dest[i] = T();
				}
			}
		};

		template<class T>
		class ListStore<T, true>
		{
		protected:
			static void CopyObjects(T* dest, const T* source, int count)
			{
				if (count)
				{
					memmove(dest, source, sizeof(T)*count);
				}
			}

			static void ClearObjects(T* dest, int count)
			{
			}
		};

		template<class T>
		class ArrayBase abstract : public ListStore<T, POD<T>::Result>, public virtual IEnumerable<T>
		{
		protected:
			class Enumerator : public Object, public virtual IEnumerator<T>
			{
			private:
				const ArrayBase<T>* container;
				int index;
			public:
				Enumerator(const ArrayBase<T>* _container, int _index = -1)
				{
					container = _container;
					index = _index;
				}
				
				IEnumerator<T>* Clone() const
				{
					return new Enumerator(container, index);
				}

				const T& Current() const
				{
					return container->Get(index);
				}

				int Index() const
				{
					return index;
				}

				bool Next()
				{
					index++;
					return index < container->Count();
				}

				void Reset()
				{
					index = -1;
				}
			};
			T* buffer;
			int count;
		public:
			ArrayBase() : buffer(nullptr), count(0) {}

			IEnumerator<T>* CreateEnumerator() const
			{
				return new Enumerator(this);
			}

			int Count() const
			{
				return count;
			}

			const T& Get(int index) const
			{
				if (index >= count || index < 0)
					throw OutOfRange();
				return buffer[index];
			}

			const T& operator[](int index) const
			{
				if (index >= count || index < 0)
					throw OutOfRange();
				return buffer[index];
			}
		};

		template<class T, class K = typename KeyType<T>::Type>
		class ListBase abstract : public ArrayBase<T>
		{
		protected:
			int capacity;
			bool lessMemoryMode;
			using ArrayBase<T>::count;
			using ArrayBase<T>::buffer;
			int CalculateCapacity(int expected)
			{
				int result = capacity;
				while (result < expected)
				{
					result = result * 5 / 4 + 1;
				}
				return result;
			}

			void MakeRoom(int index, int _count)
			{
				int newCount = count + _count;
				if (newCount > capacity)
				{
					int newCapacity = CalculateCapacity(newCount);
					T* newBuffer = new T[newCapacity];
					ListStore<T, POD<T>::Result>::CopyObjects(newBuffer, buffer, index);
					ListStore<T, POD<T>::Result>::CopyObjects(newBuffer+index+_count, buffer+index, count - index);
					delete buffer;
					capacity = newCapacity;
					buffer = newBuffer;
				}
				else
				{
					ListStore<T, POD<T>::Result>::CopyObjects(buffer + index + _count, buffer + index, count - index);
				}
				count = newCount;
			}

			void ReleaseUnnecessaryBuffer(int previousCount)
			{
				if (buffer != nullptr && count < previousCount)
				{
					ListStore<T, POD<T>::Result>::ClearObjects(&buffer[count],
						previousCount - count);
				}
				if (lessMemoryMode && count <= capacity / 2)
				{
					int newCapacity = capacity * 5 / 8;
					if (count < newCapacity)
					{
						T* newBuffer = new T[newCapacity];
						ListStore<T, POD<T>::Result>::CopyObjects(newBuffer, buffer, count);
						delete buffer;
						capacity = newCapacity;
						buffer = newBuffer;
					}
				}
			}
		public:
			ListBase() : ArrayBase(), capacity(0), lessMemoryMode(true)
			{
			}
			
			~ListBase()
			{
				delete[] buffer;
			}

			bool RemoveAt(int index)
			{
				return RemoveRange(index, 1);
			}

			bool RemoveRange(int index, int _count)
			{
				int previousCount = count;
				if (index > count || index + _count > count)
				{
					throw OutOfRange();
				}
				ListStore<T, POD<T>::Result>::CopyObjects(buffer + index, buffer + index + _count, count - index - _count);
				count -= _count;
				ReleaseUnnecessaryBuffer(previousCount);
				return true;
			}

			bool Clear()
			{
				int previousCount = count;
				count = 0;
				if (lessMemoryMode)
				{
					capacity = 0;
					delete[] buffer;
					buffer = nullptr;
				}
				else
				{
					ReleaseUnnecessaryBuffer(previousCount);
				}
				return true;
			}

			void SetLessMemoryMode(bool mode)
			{
				lessMemoryMode = mode;
			}
		};

		template<class T, class K = typename KeyType<T>::Type>
		class Array : public ArrayBase<T>
		{
		protected:
			using ArrayBase<T>::count;
			using ArrayBase<T>::buffer;
			void Create(int size)
			{
				if (size > 0) 
				{
					count = size;
					buffer = new T[size];
				}
				else
				{
					count = 0;
					buffer = nullptr;
				}
			}

			void Destory()
			{
				count = 0;
				delete[] buffer;
				buffer = nullptr;
			}

		public:
			Array(int size = 0)
			{
				Create(size);
			}

			Array(const T* _buffer, int size)
			{
				Create(size);
				ListStore<T, POD<T>::Result>::CopyObjects(ArrayBase<T>::buffer, _buffer, size);
			}

			~Array()
			{
				Destory();
			}

			bool Contains(const K& item) const
			{
				return IndexOf(item) != -1;
			}

			int IndexOf(const K& item) const
			{
				for (int i = 0; i < count; i++)
				{
					if (buffer[i] == item)
					{
						return i;
					}
				}
				return -1;
			}

			void Set(int index, const T& item)
			{
				if (index >= count || index < 0)
				{
					throw OutOfRange();
				}
				buffer[index] = item;
			}

			using ArrayBase<T>::operator[];
			T& operator[](int index)
			{
				if (index >= count || index < 0)
				{
					throw OutOfRange();
				}
				return buffer[index];
			}

			void Resize(int size)
			{
				int oldCount = count;
				T* oldBuffer = buffer;
				Create(size);
				ListStore<T, POD<T>::Result>::CopyObjects(buffer, oldBuffer, (count<oldCount?count:oldCount));
				delete[] oldBuffer;
			}
		};

		template<class T, class K = typename KeyType<T>::Type>
		class List : public ListBase<T, K>
		{
		protected:
			using ArrayBase<T>::count;
			using ArrayBase<T>::buffer;
			using ListBase<T, K>::capacity;
			using ListBase<T, K>::MakeRoom;
		public:
			List() {}
			
			bool Contains(const K& item) const
			{
				return IndexOf(item) != -1;
			}

			int IndexOf(const K& item) const
			{
				for (int i = 0; i < count; i++)
				{
					if (buffer[i] == item)
					{
						return i;
					}
				}
				return -1;
			}

			int Add(const T& item)
			{
				MakeRoom(count, 1);
				buffer[count - 1] = item;
				return count - 1;
			}

			int Insert(int index, const T& item)
			{
				if (index > count || index < 0)
				{
					throw OutOfRange();
				}
				MakeRoom(index, 1);
				buffer[index] = item;
				return index;
			}

			bool Remove(const K& item)
			{
				auto index = IndexOf(item);
				if (index < count && index >= 0)
				{
					RemoveAt(index);
					return true;
				}
				return false;
			}

			bool Set(int index, const K& item)
			{
				if (index >= count || index < 0)
				{
					throw OutOfRange();
				}
				buffer[index] = item;
			}

			using ListBase<T, K>::operator[];

			T& operator[](int index)
			{
				if (index >= count || index < 0)
				{
					throw OutOfRange();
				}
				return buffer[index];
			}

		};

		template<class T, class K = typename KeyType<T>::Type>
		class SortedList : public ListBase<T, K>
		{
		protected:
			using ArrayBase<T>::count;
			using ArrayBase<T>::buffer;
		public:
			SortedList() {}

			bool Contains(const K& item) const
			{
				return IndexOf(item) != -1;
			}

			template<class Key>
			int IndexOf(const Key& item) const
			{
				if (count == 0) {
					return -1;
				}
				int start = 0;
				int end = count - 1;
				while (start <= end)
				{
					int index = start + (end - start) / 2;
					if (buffer[index] == item)
					{
						return index;
					}
					else if (buffer[index] > item)
					{
						end = index - 1;
					}
					else
					{
						start = index + 1;
					}
				}
				return -1;
			}

			int IndexOf(const K& item) const
			{
				return IndexOf<K>(item);
			}

			int Add(const T& item)
			{
				if (count == 0)
				{
					MakeRoom(0, 1);
					buffer[0] = item;
					return 0;
				}
				else
				{
					int start = 0;
					int end = count - 1;
					int index = -1;
					while (start <= end && start >= 0 && end < count)
					{
						index = (start + end) / 2;
						if (buffer[index] == item)
						{
							goto SORTED_LIST_INSERT;
						}
						else if (buffer[index] > item)
						{
							end = index - 1;
						}
						else
						{
							start = index - 1;
						}
					}
					if (index >= count)
					{
						throw OutOfRange();
					}
					if (buffer[index] < item)
					{
						index++;
					}
				SORTED_LIST_INSERT:
					MakeRoom(index, 1);
					buffer[index] = item;
					return index;
				}
			}

			bool Remove(const K& item)
			{
				auto index = IndexOf(item);
				if (index < count && index >= 0)
				{
					RemoveAt(index);
					return true;
				}
				return false;
			}

		};
		namespace RandomAccessInternal
		{
			template<typename T, typename K>
			struct RandomAccessable<Array<T, K>>
			{
				static const bool							CanRead = true;
				static const bool							CanResize = true;
			};

			template<typename T, typename K>
			struct RandomAccessable<List<T, K>>
			{
				static const bool							CanRead = true;
				static const bool							CanResize = false;
			};

			template<typename T, typename K>
			struct RandomAccessable<SortedList<T, K>>
			{
				static const bool							CanRead = true;
				static const bool							CanResize = false;
			};
		}
	}
}

#endif // __CANVAS_COLLECTION_LIST_H